package org.ymx.myLinkedList;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author 17122
 */
public class MyLinkedList<AnyType> implements Iterable<AnyType> {

    private int size;
    /**
     * 改变次数
     */
    private int modCount = 0;

    /**
     * 头结点指针  指向上一个Node的值
     */
    private Node<AnyType> beginMarker;

    /**
     * 尾结点指针    指向下一个Node的值
     */
    private Node<AnyType> endMarker;


    /**
     * 空构造
     */
    public MyLinkedList() {
        doClear();
    }

    /**
     * 清空数组
     */
    private void doClear() {
        beginMarker = new Node<AnyType>(null, null, null);
        endMarker = new Node<AnyType>(null, beginMarker, null);
        beginMarker.next = endMarker;
        size = 0;
        modCount++;
    }

    /**
     * 返回大小
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加一个元素
     *
     * @param item
     */
    public void add(AnyType item) {
        add(size(), item);
    }

    /**
     * 向一个位置添加元素
     *
     * @param index
     * @param item
     */
    public void add(int index, AnyType item) {
        addBefore(getNode(index, 0, size), item);
    }

    /**
     * 获取一个元素
     *
     * @param index
     * @return
     */
    public AnyType get(int index) {
        return getNode(index).data;
    }

    /**
     * 获取一个节点
     *
     * @param index
     * @return
     */
    private Node<AnyType> getNode(int index) {
        return getNode(index, 0, size() - 1);
    }

    /**
     * 获取一个元素
     *
     * @param index
     * @param lower
     * @param upper
     * @return
     */
    private Node<AnyType> getNode(int index, int lower, int upper) {
        Node<AnyType> node;
        //验证是否合法
        if (index < lower || index > upper) {
            throw new IndexOutOfBoundsException();
        }
        //
        if (index < size() / 2) {
            node = beginMarker.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = endMarker;
            for (int i = size(); i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    /**
     * 替换值
     *
     * @param index
     * @param item
     * @return
     */
    public AnyType set(int index, AnyType item) {
        Node<AnyType> node = getNode(index);
        AnyType data = node.data;
        node.data = item;
        return data;
    }


    /**
     * 删除一个元素
     *
     * @param index
     * @return
     */
    public AnyType remove(int index) {
        return remove(getNode(index));
    }

    /**
     * 删除一个节点
     *
     * @param node
     * @return
     */
    private AnyType remove(Node<AnyType> node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        size--;
        modCount++;
        return node.data;
    }

    /**
     * 向头节点添加元素
     *
     * @param node
     * @param item
     */
    private void addBefore(Node<AnyType> node, AnyType item) {
        Node<AnyType> newNode = new Node<>(item, node.prev, node);
        newNode.prev.next = newNode;
        node.prev = newNode;
        size++;
        modCount++;
    }


    @Override
    public Iterator<AnyType> iterator() {
        return new LinkedListIterator();
    }

    /**
     * 迭代器内部类
     */
    private class LinkedListIterator implements Iterator<AnyType> {

        private Node<AnyType> current = beginMarker.next;

        private int expModCount = modCount;

        private boolean okToRemove = false;


        @Override
        public boolean hasNext() {
            return current != endMarker;
        }

        @Override
        public AnyType next() {
            if (modCount != expModCount) {
                throw new ConcurrentModificationException();
            }
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        @Override
        public void remove() {
            if (modCount != expModCount) {
                throw new ConcurrentModificationException();
            }
            if (!okToRemove) {
                throw new NoSuchElementException();
            }
            MyLinkedList.this.remove(current.prev);
            expModCount++;
            okToRemove = false;
        }

    }
}

